package com.gwcloud.leetcode.offers;

/** 
* @ClassName   : Leetcode0120 
* @author      : ganwei 
* @date        : 2020年5月31日 
* @Description : TODO 
*/
public class Leetcode0120 {
    /**
     * -解题思路，回溯思路
     */
	public boolean exist(char[][] board, String word) {
		int m = board.length;
		int n = board[0].length;
		for(int i = 0; i < m; i++){
			for(int j = 0; j < n; j++){
				if(backtrace(board, i, j, word, new boolean[m][n])){
					return true;
				}
			}
		}
		return false;
    }
	public boolean backtrace(char[][] board, int i, int j, String word, boolean[][] visited){
		if(word.length() == 0){
			return true;
		}
		if(board[i][j] != word.charAt(0)){
			return false;
		}
		if(board[i][j] == word.charAt(0) && word.length() == 1){
			return true;
		}
		int m = board.length;
		int n = board[0].length;
		
		if(i-1 >= 0 && i-1 < m && !visited[i-1][j]){
			visited[i-1][j] = true;
			if(backtrace(board, i-1, j, word.substring(1), visited)){
				return true;
			}
			visited[i-1][j] = false;
		}
		if(i+1 >= 0 && i+1 < m && !visited[i+1][j]){
			visited[i+1][j] = true;
			if(backtrace(board, i+1, j, word.substring(1), visited)){
				return true;
			}
			visited[i+1][j] = false;
		}
		if(j-1 >= 0 && j-1 < n && !visited[i][j-1]){
			visited[i][j-1] = true;
			if(backtrace(board, i, j-1, word.substring(1), visited)){
				return true;
			}
			visited[i][j-1] = false;
		}
		if(j+1 >= 0 && j+1 < n && !visited[i][j+1]){
			visited[i][j+1] = true;
			if(backtrace(board, i, j+1, word.substring(1), visited)){
				return true;
			}
			visited[i][j+1] = false;
		}
		
		return false;
		
	}
	
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	
    }
}
